Moskalenko sinh tại làng Grishino, tỉnh Yekaterinoslav, Đế quốc Nga (nay thuộc Krasnoyarmiisk Pokrovsk Raion, Donetsk Oblast, Ukraina), trong một gia đình nông dân người Ukraina. Ông theo học một số học viện quân sự và gia nhập Hồng quân năm 1920 và chiến đấu trên nhiều mặt trận khác nhau trong cuộc Nội chiến Nga.

Trong Chiến tranh Liên Xô-Phần Lan, ông là chỉ huy pháo binh thuộc Sư đoàn súng trường 51. Khi Chiến dịch Barbarossa bắt đầu vào tháng 6 năm 1941, Moskalenko là chỉ huy của một lữ đoàn chống tăng. Trong khoảng thời gian từ tháng 6 năm 1941 đến tháng 3 năm 1942, Moskalenko lần lượt giữ quyền các chỉ huy Lữ đoàn chống tăng số 1, Quân đoàn súng trường 15, Tập đoàn quân đoàn 6 và sau đó là Quân đoàn kỵ binh số 6. Ông là chỉ huy của Tập đoàn quân 38 mới, được cải tổ từ tháng 3 đến tháng 7 năm 1942. Sau đó, ông được bổ nhiệm làm Tư lệnh Tập đoàn quân xe tăng 1 (tháng 7 năm 1942) và Tập đoàn quân Cận vệ 1 (tháng 8 năm 1942) trước khi được chỉ định làm chỉ huy Tập đoàn quân 40, độc lập với Phương diện quân Voronezh, một vị trí ông giữ cho đến tháng 10 năm 1943. Moskalenko chỉ huy đơn vị tham gia cuộc phản công mùa đông và trong Trận Vòng cung Kursk. Vì những đóng góp của ông cho một số lượng lớn các trận đánh quan trọng, như Moskva, Stalingrad, và Kursk, Moskalenko đã được trao tặng danh hiệu Anh hùng Liên Xô.

Từ tháng 10 năm 1943 cho đến khi kết thúc chiến tranh, Moskalenko là chỉ huy của Tập đoàn quân 38. Ông chỉ huy đơn vị mình đánh đuổi quân Đức khỏi Ukraina, Ba Lan và Tiệp Khắc.

Hậu chiến

Sau chiến tranh, Moskalenko đã phục vụ trong nhiều vị trí khác nhau trong Quân khu Moskva, trước khi được bổ nhiệm làm Tư lệnh quân khu năm 1953.

Ngày 25 tháng 7 năm 1953, Nikita Khrushchev cùng với Nguyên soái Georgy Zhukov và Kirill Moskalenko đã bí mật bắt giữ Phó Thủ tướng thứ nhất của Liên Xô Lavrentiy Beria trong một cuộc họp. Trong khi Zhukov không thể mang súng vào Điện Kremli, Moskalenko đã tìm cách bí mật mang theo súng vào để bắt Beria. Trong 6 tháng sau đó, ông tham gia điều tra "Vụ án Beria". Tháng 12 năm 1953, Tòa án Tối cao Liên Xô đã tuyên án Beria phạm tội sau một quá trình tố tụng kéo dài 5 ngày. Ngày 23 tháng 12, Beria bị đưa ra xử bắn.

Ngày 11 tháng 3 năm 1955, Moskalenko, cùng với năm tướng lĩnh khác, được phong quân hàm Nguyên soái Liên Xô. Moskalenko ở lại Quân khu Moskva cho đến năm 1960, khi ông được bổ nhiệm làm Tư lệnh các lực lượng tên lửa chiến lược. Năm 1962, ông được chuyển sang làm Tổng Thanh tra Bộ Quốc phòng.

Ông qua đời ngày 17 tháng 6 năm 1985 và được chôn cất tại Nghĩa trang Novodevichy.